// Created by WXX on 2021/11/17 11:23
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：56 ms, 在所有 C++ 提交中击败了48.73%的用户
 * 内存消耗：10.4 MB, 在所有 C++ 提交中击败了83.54%的用户
 */
class Solution {
public:
    vector<int> fallingSquares(vector<vector<int>>& pos) {

        int n = pos.size();
        vector<int> h(n);
        for (int i = 0; i < n; i++) {
            // 区间[a, b], 边长为side
            int a = pos[i][0], b = a + pos[i][1], side = pos[i][1];
            h[i] += side;  // h[i]: 只考虑0~i方块，在区间[a, b]的最大高度

            for (int j = i + 1; j < n; j++) {
                int c = pos[j][0], d = c + pos[j][1];
                if (intersection(a, b, c, d))
                    h[j] = max(h[j], h[i]);
            }
        }

        vector<int> res;
        int t = 0;  // 掉落前面的方块后整个局面的最大高度
        for (int x : h) {
            t = max(t, x);
            res.push_back(t);
        }

        return res;
    }

    // 判断[a, b], [c, d]是否有交集，只相交一个点不算有交集
    bool intersection(int a, int b, int c, int d) {
        return !(c >= b || a >= d);
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<vector<int>> pos = {{1, 2}, {2, 3}, {6, 1}};
    OutputBasicArray1D(Solution().fallingSquares(pos));  // [2, 5, 5]

    return 0;
}
